package Leetcode第一期;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author : K k
 * @date : 10:05 2020/9/14
 * 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
 *
 * 请写一个函数，求任意第n位对应的数字。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：3
 * 示例 2：
 *
 * 输入：n = 11
 * 输出：0
 */
public class 数字序列中某一位的数字_44 {

    //思路1：构造一个序列 并查找对应下标，但是会超时
    //不推荐
    public static int findNthDigitA(int n) {
        List<Integer> list=new LinkedList<>();
        int a=0,b=0;//用户存放余数与商
        for (int i=0;i<=2*n;i++){
            Stack<Integer> stack=new Stack<>();
            a=i;
            while (a>0){
                b=a%10;
                a=a/10;
                stack.add(b);
            }
            while (!stack.isEmpty()){
                list.add(stack.pop());
            }
        }
        Integer[] integers = list.toArray(new Integer[n]);
        return integers[n-1];
    }

    //思路二：数学公式法
    public static int findNthDigitB(int n) {
        //开始为 1位数，开头数字为1，省略了0，第一组的数位总和是9（忽略了0，所以后面要多-1）
        /*int digital=1,start=1,count=9;
        while (n>count){
            //确定范围
            n-=count;
            digital+=1;
            start*=10;
            count=digital*start*9;  //9、180、2700....
        }
        //计算是哪个数字
        long num=start+(n-1)/digital; //-1是因为前面0忽略
        //String res = String.valueOf(num);
        //return res.charAt((n-1)%digital)-'0';
        return Long.toString(num).charAt((n - 1) % digital) - '0';*/
        int digit = 1;
        long start = 1;
        long count = 9;
        while (n > count) { // 1.
            n -= count;
            digit += 1;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit; // 2.
        return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3
    }

    public static void main(String[] args) {
        System.out.println(数字序列中某一位的数字_44.findNthDigitB(15));
    }
}
